package primenumbers;

import java.math.BigInteger;
import java.util.ArrayList;

public class Factor {
	private static final BigInteger TWO = new BigInteger("2");

	public static void main(String[] args) {
		ArrayList<BigInteger> factors = new ArrayList<BigInteger>();
		BigInteger N = new BigInteger("1000578901234567890");
		//BigInteger N = new BigInteger("9223372036854775807");
		//BigInteger N = new BigInteger("2147483647");
		//BigInteger N = new BigInteger("21");
		BigInteger root = sqrt(N);
		
		for (BigInteger d = TWO; d.compareTo(root) < 0; d = d.add(BigInteger.ONE)) {
			BigInteger x[] = N.divideAndRemainder(d);

			while (x[1].equals(BigInteger.ZERO)) {
				factors.add(d);
				N = x[0];
				x = N.divideAndRemainder(d);
			}

			if (N.equals(BigInteger.ONE)) {
				break;
			}
		}

		if (N.compareTo(BigInteger.ONE) > 0) {
			factors.add(N);
		}
	}
	
	private static BigInteger sqrt(BigInteger n) {
		BigInteger min = BigInteger.ONE;
		BigInteger max = n.divide(TWO);
		BigInteger d = null, x;

		while (max.subtract(min).compareTo(BigInteger.ONE) > 0) {
			d = max.add(min).divide(TWO);
			x = d.multiply(d);

			if (x.equals(n)) {
				return d;
			} 
			
			if (x.compareTo(n) < 0) {
				min = d;
			} else {
				max = d;
			}
		}

		return d;
	}
}